﻿/*
AVL 树  概念
	AVL树是最先发明自平衡二叉查找树，AVL是一棵空树，或者具备下列性质的二叉搜索树：
	它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一棵高度平衡搜索二叉树，
	通过控制高度差去控制平衡。（任何子树高度差都是1）
	
	每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，
	AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便进行观察和控制树是否平衡，像一个风向标。
	
	为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？
	答：因为有些情况是做不到高度差是0的。
		譬如：一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0
		
	AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN ，那么增删查改的效率也可以控制在 O(logN)，
	相比二叉搜索树有了本质的提升。



AVL树的插入
	1.插入一个值按二叉搜索树规则进行插入。
	2.新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新
	  从 新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了。
	3.更新平衡因子过程中没有出现问题，则插入结束
	4.更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树
	  的高度，不会再影响上一层，所以插入结束。


平衡因子的更新	
	更新原则：
		1.平衡因子 = 右子树高度 - 左子树高度
		2.只有子树高度变化才会影响当前结点平衡因子。
		3.插入结点,会增加高度,所以新增结点在parent的右子树,parent的平衡因子++，新增结点在parent的左子树，parent平衡因子要进行 --
		4.parent所在子树的高度是否变化决定了是否会继续往上更新

	更新停止的条件（前提：本身就是AVL树）
		1.更新后parent的平衡因子等于0，更新中parent的平衡因子变化为 -1->0 或者 1->0，说明更新前
		  parent子树一边高一边低，新增的结点插⼊在低的那边，插入后parent所在的子树高度不变，不会
		  影响parent的父亲结点的平衡因子，更新结束。
		2.更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说
		  明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所
		  在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向
		  上更新。
		3.更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为 1->2 或者 -1->-2，说
		  明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高
		  了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：
			  (1)把parent子树旋转平衡。
			  (2)降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
		4.不断更新，更新到根，根的平衡因子是 1 或 -1 也停止了
		

旋转
	旋转的原则：
		1. 保持搜索树的规则
		2. 让旋转的树从不满足变平衡
		3. 降低旋转树的高度

	旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。


左单旋就是旋转点的左子树变成旋转点父亲节点的右子树    父亲节点变成旋转点的左节点
右单旋就是旋转点的右子树变成旋转点父亲节点的左子树    父亲节点变为旋转点的右节点
左单旋用于右子树高   左子树低的情况
右单旋用于左子树高   右子树低的情况



删除操作   
	1.找到删除节点进行删除
	2.更新平衡因子
	3.旋转

*/